//{=======================================
//! @file kwork.cpp
//! @date 2014-09-22
//! @author  Artem Mikhalev <grozzmaster@gmail.com>
//}=======================================

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>

#ifdef MY_COMPUTER
    #define DBG printf ("# ");
    #define maxinput 1000000000
#else
    #define DBG if (0)
#endif


int ScanMany (), InterSection (int, int, int*);   //Problem 1
int TurnStr ();                                    //Problem 2
int divisors (), sum_divisors (int);               //Problem 3
int Repetitions ();                                //Problem 4
int MAX (int, int), Bool_Sum ();                  //Problem 5
int Matrix (), MatrixT (int*, int, int);          //Problem 6
int ThreeSquare ();                                //Problem 7
int CheckNumber (int), SimpleNumber ();            //Problem 8
int FourSquare ();                                 //Problem 9
int divisors2 ();                                  // Problem 10

int main()
{
    DBG printf ("------------------------------------------------------\n");
    DBG printf ("######################################################\n");

    DBG printf ("Problem 1 - Finding an intersection of two number sets\n");
    DBG printf ("Problem 2 - Turning string\n");
    DBG printf ("Problem 3 - To count sum of divisors of number\n");
    DBG printf ("Problem 4 - Finding repetitions among input numbers\n");
    DBG printf ("Problem 5 - Sum of binary numbers\n");
    DBG printf ("Problem 6 - Transpose of matrix\n");
    DBG printf ("Problem 7 - Sum of three squares\n");
    DBG printf ("Problem 8 - Searching simple number\n");
    DBG printf ("Problem 9 - Sum of four squares\n");
    DBG printf ("Problem 10 - Sum of divisors of input number\n");

    DBG printf ("######################################################\n");
    DBG printf ("Input the number of problem which you want to solve\n");

    int numberofproblem = 0, returnvalue = 0;
    DBG scanf ("%d", &numberofproblem);

    DBG printf ("######################################################\n");

    switch (numberofproblem)
    {
        case 1:
            DBG printf ("Problem 1 - Finding a Intersection of two number sets\n");
            DBG printf ("v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input the size of number set (N) and after that input N numbers. You should do it twice (for two sets).\n");

            returnvalue = ScanMany ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'ScanMany': %d\n", returnvalue);
            break;


        case 2:
            DBG printf ("Turning string\n");
            DBG printf ("v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input string which you want to turn\n");

            returnvalue = TurnStr ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'TurnStr': %d\n", returnvalue);
            break;

        case 3:
            DBG printf ("To count sum of divisors of number\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input a number. The program will count sum of divisors of input number\n");

            returnvalue = divisors ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'divisors': %d\n", returnvalue);
            break;

        case 4:
            DBG printf ("Finding repetitions among input numbers\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input some numbers. The program will find repetitions among these numbers\n");

            returnvalue = Repetitions ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'Repetitions': %d\n", returnvalue);
            break;

        case 5:
            DBG printf ("Sum of binary numbers\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input two binary numbers. You will see sum of these numbers!\n");

            returnvalue = Bool_Sum ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'Bool_Sum': %d\n", returnvalue);
            break;

        case 6:
            DBG printf ("Transpose of matrix\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input size of square matrix. The program will transpose the matrix\n");

            returnvalue = Matrix ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'Matrix': %d\n", returnvalue);
            break;

        case 7:
            DBG printf ("Sum of three squares\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input a number. The program will try to decompose into a sum of 3 squares\n");

            returnvalue = ThreeSquare ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'ThreeSquare': %d\n", returnvalue);
            break;

        case 8:
            DBG printf ("Searching simple number\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input number. The program will search simple number by input number\n");

            returnvalue = SimpleNumber ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'SimpleNumber': %d\n", returnvalue);
            break;

        case 9:
            DBG printf ("Sum of four squares\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input a number. The program will decompose into a sum of 4 squares\n");

            returnvalue = FourSquare ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'FourSquare': %d\n", returnvalue);
            break;

        case 10:
            DBG printf ("Sum of divisors of input number\n");
            DBG printf (" v.1.0 " __DATE__ " " __TIME__ "\n");
            DBG printf ("Please input a number. The program will count sum of input number\n");

            returnvalue = divisors2 ();

            if (returnvalue) printf("ERROR. Incorrect returning value of function 'divisors2': %d\n", returnvalue);
            break;

        default:
            printf ("ERROR. Incorrect input. Correct numbers are only from 1 up to 10\n");
            break;

    }

    DBG printf ("------------------------------------------------------\n");

    return 0;
}

// Problem 1 - B var 10
int ScanMany ()
{
    int sizemany1 = 0, sizemany2 = 0;

    scanf("%d", &sizemany1);

    int *many1 = (int*) calloc (sizemany1, sizeof (int));

    int i = 0;
    for (i = 0; i < sizemany1; i++)
        scanf("%d", &many1[i]);

    scanf("%d", &sizemany2);

    InterSection (sizemany1, sizemany2, many1);

    return 0;
}


int InterSection (int sizemany1, int sizemany2, int *many1)
{
    assert (0 < sizemany1 && sizemany1 <= maxinput);
    assert (0 < sizemany2 && sizemany2 <= maxinput);
    assert (many1);

    int i = 0, j = 0, elementofmany2 = 0;

    for (i = 0; i < sizemany2; i++)
    {
        scanf("%d", &elementofmany2);

        for (j = 0; j < sizemany1; j++)
        {
            if (many1[j] == elementofmany2)
                printf("%d ", elementofmany2);
        }
    }

    printf ("\n");
    return 0;
}

// Problem 2 - C var 4
int TurnStr ()
{
    char str[1010];
    gets (str);

    printf("%s\n", str);

    int length = 0, i = 0, j = 0, s = 0;

    length = strlen (str);
    str [length] = ' ';

    for (i = 0; i <= length; i++)
    {
        if (str[i] != ' ')
            s++;

        else
        {
            for (j = 1; j <= s; j++)
                printf ("%c", str [i - j]);

            s = 0;

            if (i != length)
                printf ("%c", str [i]); //str[i] is ' ';

        }
    }

    return 0;
}

//Problem 3 - B var 5
int divisors ()
{
    int N = 0, answer = 0;
    scanf ("%d", &N);

    answer = sum_divisors (N);

    if (answer == -1)
        printf("ERROR. Incorrect returning value of function 'sum_divisors': -1\n");
    else
        printf("%d\n", answer);

    return 0;
}


int sum_divisors (int N)
{
    assert (0 < N && N <= maxinput);

    int i = 0, n = 0, sum = 0;
    n = sqrt(N);
    if (N == 1)
        return 1;

    else
    {
        for (i = 1; i <= n; i++)
        {
            if (N % i == 0)
                sum = sum + i + N/i;
        }

        return sum;
    }

    return -1;
}

//Problem 4 - B var 9
int Repetitions ()
{
    int n = 0, i = 0, j = 0, searchnum = 0, repetition = 0;

    scanf("%d", &n);

    int *numbers = (int*) calloc (n, sizeof (int));

    for (i = 0; i < n; i++)
        scanf ("%d", numbers + i);

    for (i = 0; i < n; i++)
    {
        repetition = 0;
        searchnum = *(numbers + i);

        for (j = 0; j < n; j++)
        {
            if (searchnum == numbers [j] && numbers [j] != -1)
            {
                repetition++;
                numbers [j] = -1;
            }
        }

        if (repetition > 1)
            printf ("%d %d\n", searchnum, repetition);
    }

    free (numbers);

    return 0;
}


//Problem 5 - C var 9
int MAX (int a, int b)
{
    assert (0 <= a && a <= 1000);
    assert (0 <= b && b <= 1000);

    if (a > b)
        return a;
    else
        return b;
}

int Bool_Sum ()
{
    int i = 0, s = 0, length_a = 0, length_b = 0, maxlength = 0;
    char a [1010], b [1010], ans[1010];

    scanf ("%s", a);
    scanf ("%s", b);

    length_a = strlen (a);
    length_b = strlen (b);

    maxlength = MAX (length_a, length_b);

    for (i = 0; i <= maxlength; i++)
        ans [i] = '0';

    for (i = 0; i < maxlength; i++)
    {
        if (length_a - i >= 1 && length_b - i >= 1)
        {
            ans [maxlength - i] = (char) (((int) a[length_a - i - 1] + (int) b[length_b - i - 1] + s) % 2 + (int) '0');
            if ((int) a[length_a - i - 1] + (int) b[length_b - i - 1] + s - (int) '0' - (int) '0' > 1)
                s = 1;
            else
                s = 0;

        }

        else
        {
            if (length_a - i >= 1)
            {
                ans [maxlength - i] = (char) (((int) a[length_a - i - 1] + (int) '0' + s) % 2 + (int) '0');
                if ((int) a[length_a - i - 1] + (int) '0' + s - (int) '0' - (int) '0' > 1)
                    s = 1;
                else
                    s = 0;
            }

            else
            {
                ans [maxlength - i] = (char) (((int) '0' + (int) b[length_b - i - 1] + s) % 2 + (int) '0');
                if ((int) '0' + (int) b[length_b - i - 1] + s - (int) '0' - (int) '0' > 1)
                    s = 1;
                else
                    s = 0;
            }
        }
    }

    if (s)
        printf("1");
    for (i = 1; i <= maxlength; i++)
        printf("%c", ans [i]);

    printf("\n");
    return 0;
}


//Problem 6 - A var 2
int Matrix ()
{
    int nsquare = 0, nsquare2 = 0;
    scanf ("%d", &nsquare);

    nsquare2 = nsquare * nsquare;
    int *matrix = (int*) calloc (nsquare2, sizeof (int));

    MatrixT (matrix, nsquare, nsquare2);

    free (matrix);

    return 0;
}


int MatrixT (int* matrix, int nsquare, int nsquare2)
{
    assert (matrix);
    assert (0 <= nsquare && nsquare <= maxinput);
    assert (0 <= nsquare2 && nsquare2 <= maxinput);

    int i = 0, j = 0;
    for (i = 0; i < nsquare2; i++)
        scanf ("%d", matrix + i);

    for (i = 0; i < nsquare; i++)
    {
        for (j = 0; j < nsquare; j++)
            printf ("%d ", matrix[i + j*nsquare]);

        printf("\n");
    }

}


//Problem 7 - C var 10
int ThreeSquare ()
{
    int N = 0, n = 0, m = 0, a = 0, b = 0, c = 0;

    scanf ("%d", &N);

    n = sqrt (N);

    for (a = 1; a <= n; a++)
    {
        m = sqrt (N - a*a);

        for (b = 1; b <= m; b++)
        {
            c = sqrt (N - a*a - b*b);
            if(N - a*a - b*b == c * c)
            {
                printf ("%d %d %d\n", a*a, b*b, c*c);
                return 0;
            }
        }
    }

    printf("-1\n");
}



//Problem 8 - C var 2
int CheckNumber (int N)
{
    assert (0 < N && N <= maxinput);

    int j = 0, h = 0;
    h = sqrt (N);
    for (j = 2; j <= h; j++)
    {
        if(N % j == 0)
            return 0;
    }

    return 1;
}

int SimpleNumber ()
{
    int number = 0, i = 1, N = 3;

    scanf ("%d", &number);

    if (number == 1)
    {
        printf ("2\n");
        return 0;
    }

    else
    {
        while (i < number)
        {
            if (CheckNumber (N))
                i++;

            N = N + 2;
        }
    }

    printf ("%d\n", N - 2);

    return 0;
}


//Problem 9 - C var 3
int FourSquare ()
{
    int N = 0, n = 0, m = 0, k = 0;

    scanf ("%d", &N);

    n = sqrt (N);

    int a = 0, b = 0, c = 0, d = 0;

    for (a = 1; a <= n; a++)
    {
        m = sqrt (N - a*a);

        for (b = 1; b <= m; b++)
        {
            k = sqrt (N - a*a - b*b);

            for (c = 1; c <= k; c++)
            {
                d = sqrt (N - a*a - b*b - c*c);

                if(d*d == N - a*a - b*b - c*c)
                {
                    printf ("%d %d %d %d\n", a*a, b*b, c*c, d*d);
                    return 0;
                }
            }
        }
    }

    return 0;
}


//Problem 10 - B var 5
int divisors2 ()
{
    int N = 0;

    scanf ("%d", &N);

    printf ("%d\n", sum_divisors (N));

    return 0;
}
